package dp.mincostTickets;

/**
 * @Date 2020/05/07
 * @author 王光浩
 * @Thinking 使用递归。
 *  参数：上次一个买票的下标preIndex，上一次买票时买的天数days,当前总票价数 total
 *  basic case：如果 preIndex 等于数组的最后一个下标或者 在没有查找下一个需要买票的日期。
 *  主体：根据 preIndex 获取买票的日期 date，然后在旅行计划中找到第一个大于等于的 date+days 的下标
 *  	  index然后 进行三次递归，每次递归的参数为 index,j,total+cost[j] ——其中 j 购买票的生效日期
 * @Analysis 时间复杂度O（3^n），空间复杂度O（n）
 * 
 */
public class MyMethodOne {
	private int[] cost;
	private int[] day;
	private int minCost = Integer.MAX_VALUE;

	public int mincostTickets(int[] days, int[] costs) {
		if (days == null)
			return -1;
		cost = costs;
		day = days;
		helper(0, 1 , cost[0]);
		helper(0, 7 , cost[1]);
		helper(0, 30 , cost[2]);
		return this.minCost;
	}

	private void helper(int preIndex, int days, int total) {
		if (preIndex >= day.length - 1) {
			minCost = Math.min(minCost, total);
			return;
		}
		int nextIndex = preIndex + 1;
		int target = day[preIndex] + days;
		while (nextIndex < day.length && day[nextIndex] < target)
			nextIndex++;
		if (nextIndex >= day.length) {
			minCost = Math.min(minCost, total);
			return ;
		}
		helper(nextIndex, 1, cost[0]+total);
		helper(nextIndex, 7, cost[1]+total);
		helper(nextIndex, 30, cost[2]+total);
	}
}
